线段树是什么？？线段树怎么写？？

如果你在考提高组前一天还在问这个问题，那么你会与一等奖失之交臂；如果你还在冲击普及组一等奖，那么这篇博客会浪费你人生中宝贵的5~20分钟。

上面两句话显而易见，线段树这个数据结构是一个从萌新到正式OI选手的过渡，是一个非常重要的算法，也是一个对于萌新来说较难的算法。不得不说，我学习了这个算法5遍左右才有勇气写的这篇博客。

但是，对于OI正式选手来说，线段树不是算法，应该是一种工具。她能把一些对于区间（或者线段）的修改、维护，从O(N)的时间复杂度变成O（logN）。

废话不说，这篇博客会分为四部：

第一部：线段树概念引入

第二部：简单(无pushdown）的线段树

第三部：区间+/-修改与查询

第四部：区间乘除修改与查询

 总结

第一部 概念引入

线段树是一种二叉树，也就是对于一个线段，我们会用一个二叉树来表示。比如说一个长度为4的线段，我们可以表示成这样：

这是什么意思呢？ 如果你要表示线段的和，那么最上面的根节点的权值表示的是这个线段1~4的和。根的两个儿子分别表示这个线段中1~2的和，与3~4的和。以此类推。

然后我们还可以的到一个性质：节点i的权值=她的左儿子权值+她的右儿子权值。因为1~4的和就是等于1~2的和+2~3的和。

根据这个思路，我们就可以建树了，我们设一个结构体tree，tree[i].l和tree[i].r分别表示这个点代表的线段的左右下标，tree[i].sum表示这个节点表示的线段和。

我们知道，一颗二叉树，她的左儿子和右儿子编号分别是她*2和她*2+1

再根据刚才的性质，得到式子：tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;就可以建一颗线段树了！代码如下：

嗯，这就是线段树的构建，你可能会问为什么要开好几倍的内存去储存一条线段。这是因为我们还没有让这个过大的数组干一些实事，那么什么是实事呢？让我们进入下一部（在你看懂这一部的情况下）

第二部 简单（无pushdown）的线段树

1、单点修改，区间查询

其实这一章开始才是真正的线段树，我们要用线段树干什么？答案是维护一个线段（或者区间），比如你想求出一个1~100区间中，4~67这些元素的和，你会怎么做？朴素的做法是for(i=4;i=l && tree[i].r=l) s+=search(i*2,l,r);//如果这个区间的左儿子和目标区间又交集，那么搜索左儿子 if(tree[i*2+1].l